package cn.hughie.str;

import java.util.Arrays;

/**
 * KMP子串查找算法
 *
 * @author yuh
 * @date 2018/5/21 14:31
 */
public class KMP {

    public static void getNextArray(String ptr, int[] next) {
        int length = ptr.length();
        next[0] = -1;
        int k = -1;
        int j = 0;
        char[] chars = ptr.toCharArray();
        while (j < length - 1) {
            if (k == -1 || chars[k] == chars[j]) {
                j++;
                k++;
                if(chars[j] != chars[k]){
                    next[j] = k;
                }else{
                    next[j] = next[k];
                }
            } else {
                k = next[k];
            }
        }
    }

    public static int indexOf(String str, String ptr) {
        int[] next = new int[ptr.length()];
        getNextArray(ptr, next);
        System.out.println(Arrays.toString(next));

        char[] ss = str.toCharArray();
        char[] ps = ptr.toCharArray();
        int j = 0;
        int i = 0;
        while (i < ss.length && j < ps.length) {
            if (j == -1 || ss[i] == ps[j]) {
                j++;
                i++;
            } else {
                j = next[j];
            }
        }

        if (j == ptr.length()) {
            return i - j;
        } else {
            return -1;
        }

    }


    public static void BDConvertToGD(String lng, String lat) {
        final double x_pi = 3.14159265358979324 * 3000.0 / 180.0;
        double x = Double.parseDouble(lng) - 0.0065, y = Double.parseDouble(lat) - 0.006;
        double z = Math.sqrt(x * x + y * y) - 0.00002 * Math.sin(y * x_pi);
        double theta = Math.atan2(y, x) - 0.000003 * Math.cos(x * x_pi);
        double gd_lng = z * Math.cos(theta);
        double gd_lat = z * Math.sin(theta);
        System.out.println(gd_lng+","+gd_lat);
    }

    public static void main(String[] args) {
       // int i = indexOf("xbax", "ax");
       // System.out.println(i);
        // 116.484757,39.914492
        BDConvertToGD("116.484757","39.914492");

    }
}


